Міністерство освіти І науки України
національний університет “Львівська політехніка”
Звіт по л.р. №3
Застосування генетичних алгоритмів для вирішення задачі комівояжера
Виконав: студент гр. КСМ-5
Львів – 2004
Мета: ознайомитись з методами вирішення задач за допомогою генетичних алгоритмів та використати даний алгоритм для вирішення задачі комівояжера.
Основні теоретичні відомості
Еволюційні підходи до рішення наукових проблем
Використовуючи дарвіністську теорію походження життя, учені знайшли спосіб використання її принципів для рішення різних проблем.
ПРИНЦИП ЕВОЛЮЦІЇ - це головний біологічний фактор, що поєднує всі організми в історичний ланцюг подій. Кожен об'єкт у цьому ланцюзі є результатом серії "випадків", що відбувалися під впливом селективних факторів навколишнього середовища. Протягом багатьох поколінь випадкові зміни і природний добір додавали визначені обриси поводженню елементів співтовариства, щоб якнайкраще пристосується до середовища, що оточується, що змінюється.
Такі зміни можуть бути досить екстраординарними, чергове підтвердження, що еволюція творча. Незважаючи на те, що еволюція не має строго визначеної внутрішньої мети - це ефект фізичних законів, що впливають на популяцію індивідів і на кожен індивід окремо - вона створює рішення проблеми виживання, унікальні для кожного індивіда, і ці рішення геніальні.
Представте скількох корисного можна зробити, промоделювавши процес еволюції на комп'ютері. Еволюційне моделювання може надати кошти для рішення комплексних інженерних задач (з використанням хаотичних збурювань, ймовірнісного підходу, складної нелінійної динаміки), які не можна було вирішити традиційними методами. Уже з цієї причини ця область є однієї із самих швидко розвиваються в області комп'ютерних технологій; вона розглядає проблеми, що раніше не мали задовільного рішення, такі як, швидка розробка нових лікарських препаратів, гнучкі рішення задачі керування доставкою товарів, швидкий розрахунок тактики оборони при боях, і т.д. У майбутньому може здійснитися мрія штучного інтелекту: комп'ютер буде самонавчатися і зможе стати експертом у будь-якій обраній області.
Результати виконання завдання (для 20 міст)
Розглядається випадок для 20 міст із початковою популяцією 100 осіб і 1000 циклію розмноження.
Тест 1.
Тест 2.
Висновок: таким чином дана лабораторна робота дала можливість ознайомитися з одним із методів вирішення задач оптимізації – генетичними алгоритмами. В якості тестової задачі розглядалася задача комівояжера, для якої було розроблено програму на основі еволюційного підходу і проведено ряд тестів. Аналізуючи результати можна сказати, якщо і отримані результати є не оптимальними, але вони є дуже близькими до таких.
Лістінг програми:
#include <stdio.h>
#include <graphics.h>
#include <alloc.h>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
#include <math.h>
#define СITIES 20
#define POPULATION 100
#define MUTATION 0
#define CROSSOVER 5
#define GENERATIONS 1000
#define RADIUS 2
#define MAXX 640
#define MAXY 480
int city_x[CITIES], city_y[CITIES];
double estimation[POPULATION*2];
int estimation_index[POPULATION*2];
int* buffer;
int* generate_population(){
int i,j,k,city_exist,z;
int *p,*pp;
int individuum[CITIES];
for (i=0; i<CITIES; i++){
city_x[i]=random(MAXX);
city_y[i]=random(MAXY);
}
p=(int*)calloc(2*POPULATION, CITIES*sizeof(int));
for (i=0; i<POPULATION ;i++){
for (j=0; j<CITIES; j++) individuum[j]=0;
for (j=0; j<CITIES; j++){
k=random(CITIES);
while (individuum[k]) k=(k+1)%CITIES;
individuum[k]=1;
*(p+i*CITIES+j)=k;
}
}
return p;
}
void mutuate(int* a){
int k,x1,x2;
k=random(100);
if (k<MUTATION){
x1=random(CITIES);
x2=random(CITIES);
k=a[x1];
a[x1]=a[x2];
a[x2]=k;
}
}
void correct(int* res,int k){
int i,single_gene[CITIES],element,z,l;
...
